package jjn.round2;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jiang Jining
 * @since 2023-06-10 16:34
 */
public class LeetCode17_LetterCombinationsOfAPhoneNumber {
    
    /**
     * 0-""
     * 1-""
     * 2-"abc"
     * 3-"def"
     * 4-"ghi"
     * 5-"jkl"
     * 6-"mno"
     * 7-"pqrs"
     * 8-"tuv"
     * 9-"wxyz"
     */
    private static final String[] LETTER_MAP = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        backtrack(0, digits, result, new StringBuilder());
        return result;
    }
    
    private void backtrack(int startIndex, String digits, List<String> result, StringBuilder stringBuilder) {
        if (startIndex > digits.length()) {
            return;
        }
        if (startIndex == digits.length()) {
            result.add(stringBuilder.toString());
            return;
        }
        char c = digits.charAt(startIndex);
        String letters = LETTER_MAP[c - '0'];
        for (int i = 0; i < letters.length(); i++) {
            stringBuilder.append(letters.charAt(i));
            backtrack(startIndex + 1, digits, result, stringBuilder);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
    }
}
